/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2 
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  // if (l1 == null || l2 == null){
  //     return l1 || l2;
  // }
  // let dum =new ListNode(0)
  // if(l1.val<l2.val){
  //     dum.next = l1
  //     dum.next.next=mergeTwoLists(l2,l1.next)
  // }else{
  //  dum.next = l2
  //  dum.next.next=mergeTwoLists(l1,l2.next)
  // }

  // return dum.next

  //解法二。 双指针方法
  // 创建一个虚拟列表 dum
  // 循环条件：l1&l2不为空
  // 当l1<l2时，dum的next为l1，l1向前走一步
  // 当l1>l2时，dum的next为l2，l2向前走一步
  // dum也向前走一步
  // 哪个不为空，则剩下的元素接到dum的next

  let dum = new ListNode(0)
  let cur = dum

  while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
      cur.next = l1
      l1 = l1.next
    } else {
      cur.next = l2
      l2 = l2.next
    }
    cur = cur.next
  }
  cur.next = l1 !== null ? l1 : l2
  return dum.next

};